/* Universidad del Valle de Guatemala
 * Laboratorio 3
 * Mariana Castillo
 * Luis Alburez
 * Jose Pablo Rodriguez
 * Julio Maldonado
 * Jose De La Cruz 
 * Fuente Citada: Duane A. Bailey. 2007. Java Structures. Root 7 Edition. PP. 128
 * Fecha: 28/07/13
 */

package hoja3;

import java.util.*; 
public class MergeSort{
    
  public boolean test(int n[]){ 
    for(int i = 1; i < n.length;i++) 
      if(n[i-1] > n[i]) 
      return false; 
    return true;   
  } 
   
  public int[] sort(int []n){ 
    int i = 1; 
    for(i = 1; i < n.length;i*=2){ 
      for(int j = 0;j < n.length; j += i){ 
        int p = i >> 1; 
        merge(n,j,j+p-1,j+p,j+p+p-1); 
      } 
    } 
    merge(n,0,i/2 - 1,i/2,n.length); 
    return n; 
  } 
   
  public static void merge(int [] n,int a,int b,int c,int d){ 
    d = Math.min(d,n.length-1);    
    int mer [] = new int[d-a + 1]; 
    int idx = 0; 
    int or = a; 
    while( idx < mer.length) 
      if((a>b ?false: (c>d? true : n[a] <= n[c]))) 
        mer[idx++] = n[a++];         
      else 
        mer[idx++] = n[c++];                
       
    for(int i = 0; i < mer.length; i++) 
      n[or + i] = mer[i]; 
    
    
  }

   
    
}
